#include <iostream>
//KMP模式匹配算法，最为关键的就是要求出模式的next值
using namespace std;
#include <string.h>

void get_next(char* str, int* next);
int index_KMP(char* str, char* substr);//如果主串中存在substr子串，返回子串在字符中的位置，否则返回0；
void get_nextVal(char* str, int* next);

int main()
{
    char str[102] = {'\0'};
    fgets(str, 102, stdin);
    size_t len = strlen(str);
    str[--len] = '\0'; 
    /*char sub[102] = { '\0' };
    fgets(sub, 102, stdin);
    size_t lenSub = strlen(sub);
    sub[--lenSub] = '\0';
    cout << index_KMP(str, sub) << endl;*/
    int next[102] = { 0 };
    get_next(str, next);
    for (int i = 0; i < len; i++)
        cout << next[i] + 1 << ' ';
    cout << endl;

    return 0;
}

void get_next(char* str, int* next)
{
    next[0] = -1;//将第一个字符的next值定为-1，作为结束条件
    int k = -1, i = 1;//k表示第i-1个字符的next的值，即当第i个字符不匹配时，应该让模式串的第next[i]个元素进行比较
    while (str[i] != '\0')
    {
        if (k == -1 || str[i-1] == str[k])
        {//k==-1代表模式串的第1个字符也不匹配
            k++;
            next[i] = k;
            ++i;
        }
        else
        {
            k = next[k];
        }
    }
}

void get_nextVal(char* str, int* next)
{
    next[0] = -1;
    int k = -1;
    int i = 1;
    while (str[i] != '\0')
    {
        if (-1 == k || str[i - 1] == str[k])
        {
            k++;
            if (str[i] == str[k])
                next[i] = next[k];
            else
                next[i] = k;
            i++;
        }
        else
        {
            k = next[k];
        }
    }
}

int index_KMP(char* str, char* substr)
{
    size_t len = strlen(substr);
    int* next = (int*)malloc(sizeof(int) * len);
    if (NULL == next)
    {
        perror("malloc fail");
        return -1;
    }
    get_nextVal(substr, next);
    for (int i = 0; i < len; i++)
    {
        cout << next[i] << ' ';
    }
    cout << endl;
    int i = 0, j = 0;
    while (1)
    {
        if (j == -1 || str[i] == substr[j])
        {
            i++, j++;
        }
        else
        {
            j = next[j];
        }
        if ('\0' == str[i] || (j != -1 && '\0' == substr[j]))
            break;
    }
    int ret = 0;
    if (j != -1 && '\0' == substr[j])
        ret = i - j + 1;
    else 
        ret = 0;
    return ret;
}
